package io.zhengsh.vvip.leetcode.findandsort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56. 区间合并
 *
 */
public class Q56_Merge_Intervals {

    class Solution {
        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return new int[0][2];
            }

            // 排序
            Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));

            List<int[]> merged = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                int left = intervals[i][0], right = intervals[i][1];
                // 第一次 || 区间不重叠(oldMax < newMin)
                if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < left) {
                    merged.add(new int[]{left, right});
                } else {
                    // 可以合并的集合，合并最后一个集合的右边即可
                    merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], right);
                }
            }
            return merged.toArray(new int[merged.size()][]);
        }
    }
}
